package q1631_minimumEffortPath;

import CommonClass.UF;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Solution {
    int rows, cols;
    /*
    并查集解法：
    将heights的一个个格子视为一个个节点，通过一个list记录每两个格子之间具有的权重：也就是高低差
    然后通过排序的方式将list按照权重从小到大进行排序，接下来构建并查集
    我们期望获得的是一条路径，其中每两个点的高低差都不大于最大的高低差，且希望这个最大的高低差取最小值
    那么在遍历的过程中，由于本来就是从小到大进行排序，那么每次遍历到一组新的节点，就将其union
    代表着当前小于等于该高低差的所有相邻节点都被合并成了可能不同的一些簇
    而直到一组节点时，发现0号格子和最后一号格子已经被合并到了同一个簇中，此时就找到了最小所需的高低差
     */
    public int minimumEffortPath(int[][] heights) {
        List<int[]> edges = new ArrayList<>();
        rows = heights.length;
        cols = heights[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i > 0) edges.add(new int[]{getIndex(i - 1, j), getIndex(i, j), Math.abs(heights[i][j] - heights[i - 1][j])});
                if (j > 0) edges.add(new int[]{getIndex(i, j - 1), getIndex(i, j), Math.abs(heights[i][j] - heights[i][j - 1])});
            }
        }
        edges.sort(Comparator.comparingInt(edge -> edge[2]));
        UF uf = new UF(rows * cols);

        for (int[] edge : edges) {
            int x = edge[0], y = edge[1], weight = edge[2];
            uf.union(x, y);

            if (uf.isConnected(0, rows * cols - 1)) {
                return weight;
            }
        }
        return 0;
    }

    private int getIndex(int i, int j) {
        return i * cols + j;
    }
}
